<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(B卷,100分)- 阿里巴巴找黄金宝箱(II)（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>一贫如洗的樵夫阿里巴巴在去砍柴的路上&#xff0c;无意中发现了强盗集团的藏宝地&#xff0c;藏宝地有编号从0-N的箱子&#xff0c;每个箱子上面贴有箱子中藏有金币的数量。</p> 
<p>从金币数量中选出一个数字集合&#xff0c;并销毁贴有这些数字的每个箱子&#xff0c;如果能销毁一半及以上的箱子&#xff0c;则返回这个数字集合的最小大小</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>一个数字字串&#xff0c;数字之间使用逗号分隔&#xff0c;例如&#xff1a;6,6,6,6,3,3,3,1,1,5</p> 
<p>字串中数字的个数为偶数&#xff0c;并且</p> 
<ul><li>1 ≤ 字串中数字的个数 ≤ 100000</li><li>1 ≤ 每个数字 ≤ 100000</li></ul> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>这个数字集合的最小大小&#xff0c;例如: 2</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">1,1,1,1,3,3,3,6,6,8</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">2</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"> <p>选择集合{1,8}&#xff0c;销毁后的结果数组为[3,3,3,6,6]&#xff0c;长度为5&#xff0c;长度为原数组的一半。</p> <p>大小为 2 的可行集合还有{1,3},{1,6},{3,6}。<br /> 选择 {6,8} 集合是不可行的&#xff0c;它销后的结果数组为[1,1,1,1,3,3,3]&#xff0c;新数组长度大于原数组的二分之一。</p> </td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">2,2,2,2</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">1</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">我们只能选择集合{2}&#xff0c;销毁后的结果数组为空。</td></tr></tbody></table> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题主要考察贪心思维。</p> 
<p></p> 
<p>本题中有几个数字的概念&#xff1a;</p> 
<ul><li>箱子上贴的数字</li><li>箱子中金币数量</li><li>箱子的个数</li></ul> 
<p>其中&#xff0c;箱子上贴的数字就是箱子中金币数量&#xff0c;这里我们可以将这两个概念合并为一个箱子的类别</p> 
<ul><li>箱子的类别&#xff08;等价于箱子上贴的数字&#xff0c;等价于箱子中金币数量&#xff09;</li><li>箱子的个数</li></ul> 
<p></p> 
<p>我们需要统计 各个类别的出现次数。</p> 
<p>然后&#xff0c;对这些类别按照出现次数进行降序排序&#xff0c;即第一个类别的箱子的出现次数最多。</p> 
<p></p> 
<p>本题想要销毁最多的箱子&#xff0c;但是又要尽可能保留最多类别&#xff0c;因此根据贪心原则&#xff0c;我们应该优先销毁出现次数最多的类别&#xff0c;这样就能保证销毁最少的类别&#xff0c;但是可以销毁更多的箱子&#xff0c;让销毁的箱子数量尽快达到总数的一半及以上。</p> 
<p>我们最后返回销毁的类别的数量即可。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">Java算法源码</h4> 
<pre><code class="language-java">import java.util.*;
import java.util.stream.Collectors;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);
    int[] nums &#61; Arrays.stream(sc.nextLine().split(&#34;,&#34;)).mapToInt(Integer::parseInt).toArray();
    System.out.println(getResult(nums));
  }

  public static int getResult(int[] nums) {
    // 箱子上贴的数字可以看出 类别
    // 统计每一个类别出现的次数&#xff0c;key是类别&#xff0c;value是类别出现次数
    HashMap&lt;Integer, Integer&gt; count &#61; new HashMap&lt;&gt;();

    for (int num : nums) {
      count.put(num, count.getOrDefault(num, 0) &#43; 1);
    }

    // half是箱子数量的一半&#xff0c;注意向上取整&#xff0c;因为比如箱子有7个&#xff0c;则销毁一半及以上的箱子数量至少是4个&#xff0c;而不是3个
    int half &#61; (int) Math.ceil(nums.length / 2.0);

    // 按类别出现次数降序 类别
    List&lt;Map.Entry&lt;Integer, Integer&gt;&gt; collect &#61;
        count.entrySet().stream()
            .sorted((a, b) -&gt; b.getValue() - a.getValue())
            .collect(Collectors.toList());

    // remove记录销毁的箱子数量
    int remove &#61; 0;
    // numCount记录销毁的类别数量
    int numCount &#61; 0;
    // 贪心思维,想要销毁最多的箱子数&#xff0c;又要销毁的箱子的类别数最少&#xff0c;则应该尽可能销毁出现次数多的类别&#xff0c;因此前面对按照次数降序了类别
    for (Map.Entry&lt;Integer, Integer&gt; entry : collect) {
      remove &#43;&#61; entry.getValue();
      numCount&#43;&#43;;
      // 一旦达标&#xff0c;则返回销毁的类别数量
      if (remove &gt;&#61; half) {
        return numCount;
      }
    }

    return -1; // 走不到此行&#xff0c;仅用于代码健壮性
  }
}
</code></pre> 
<h4>JS算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on(&#34;line&#34;, (line) &#61;&gt; {
  const nums &#61; line.split(&#34;,&#34;).map(Number);
  console.log(getResult(nums));
});

function getResult(nums) {
  // 箱子上贴的数字可以看成 类别
  // 统计每一个类别出现的次数&#xff0c;key是类别&#xff0c;value是类别出现次数
  const count &#61; {};

  for (let num of nums) {
    count[num] &#61; (count[num] ?? 0) &#43; 1;
  }

  // half是箱子数量的一半&#xff0c;注意向上取整&#xff0c;因为比如箱子有7个&#xff0c;则销毁一半及以上的箱子数量至少是4个&#xff0c;而不是3个
  const half &#61; Math.ceil(nums.length / 2);

  // 按类别出现次数降序 类别
  const sortedEntery &#61; Object.entries(count).sort((a, b) &#61;&gt; b[1] - a[1]);

  // remove记录销毁的箱子数量
  let remove &#61; 0;
  // numCount记录销毁的类别数量
  let numCount &#61; 0;

  // 贪心思维,想要销毁最多的箱子数&#xff0c;又要销毁的箱子的类别数最少&#xff0c;则应该尽可能销毁出现次数多的类别&#xff0c;因此前面对按照次数降序了类别
  for (let entry of sortedEntery) {
    remove &#43;&#61; entry[1];
    numCount&#43;&#43;;
    // 一旦达标&#xff0c;则返回销毁的类别数量
    if (remove &gt;&#61; half) {
      return numCount;
    }
  }

  return -1; // 走不到此行&#xff0c;仅用于代码健壮性
}
</code></pre> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
import math

nums &#61; list(map(int, input().split(&#34;,&#34;)))


# 算法入口
def getResult():
    # 箱子上贴的数字可以看成 类别
    # 统计每一个类别出现的次数&#xff0c;key是类别&#xff0c;value是类别出现次数
    count &#61; {}

    for num in nums:
        count[num] &#61; count.get(num, 0) &#43; 1

    # half是箱子数量的一半&#xff0c;注意向上取整&#xff0c;因为比如箱子有7个&#xff0c;则销毁一半及以上的箱子数量至少是4个&#xff0c;而不是3个
    half &#61; int(math.ceil(len(nums) / 2))

    # 按类别出现次数降序 类别
    entries &#61; list(count.items())
    entries.sort(key&#61;lambda x: -x[1])

    # remove记录销毁的箱子数量
    remove &#61; 0
    # numCount记录销毁的类别数量
    numCount &#61; 0

    # 贪心思维,想要销毁最多的箱子数&#xff0c;又要销毁的箱子的类别数最少&#xff0c;则应该尽可能销毁出现次数多的类别&#xff0c;因此前面对按照次数降序了类别
    for entry in entries:
        remove &#43;&#61; entry[1]
        numCount &#43;&#61; 1
        # 一旦达标&#xff0c;则返回销毁的类别数量
        if remove &gt;&#61; half:
            return numCount

    return -1  # 走不到此行&#xff0c;仅用于代码健壮性


# 算法调用
print(getResult())
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>